ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/subseq/main.cpp

   1 #include <vector>
   2 #include <string>
   3 #include <iostream>
   4 #include <cassert>
   5 #include <cstdio>
   6
   7 using namespace std;
   8
   9 typedef unsigned int uint32;
  10
  11 #define forsn(i, s, n)  for (uint32 i = (s); i < (n); i++)
  12 #define forn(i, n)      forsn (i, 0, n)
  13 #define dforn(i, n)     for (uint32 i = (n); i-- > 0;)
  14
  15 // BigInt
  16 // Represents a number in 0 <= n < 10 ** 128
  17
  18 #define BigInt_NDIGITS  16
  19 #define BigInt_BASE     100000000
  20 class BigInt {
  21 public:
  22         BigInt() : _digits(BigInt_NDIGITS, 0) {}
  23
  24         BigInt(uint32 n) : _digits(BigInt_NDIGITS, 0) {
  25                 assert(n < BigInt_BASE);
  26                 _digits[0] = n;
  27         }
  28
  29         // For testing
  30         BigInt(const string& s) : _digits(BigInt_NDIGITS, 0) {
  31                 uint32 pow = 1;
  32                 uint32 digit = 0;
  33                 uint32 j = 0;
  34                 dforn (i, s.size()) {
  35                         assert('0' <= s[i] && s[i] <= '9');
  36                         digit += pow * (s[i] - '0');
  37
  38                         pow *= 10;
  39                         if (pow == BigInt_BASE) {
  40                                 _digits[j++] = digit;
  41                                 digit = 0;
  42                                 pow = 1;
  43                         }
  44                 }
  45                 assert(j < BigInt_NDIGITS || digit == 0);
  46                 if (j < BigInt_NDIGITS) {
  47                         _digits[j] = digit;
  48                 }
  49         }
  50
  51         BigInt operator+(const BigInt& n) {
  52                 BigInt res;
  53                 bool carry = 0;
  54
  55                 forn (i, BigInt_NDIGITS) {
  56                         const uint32 r = _digits[i] + n._digits[i] + carry;
  57                         if (r >= BigInt_BASE) {
  58                                 res._digits[i] = r % BigInt_BASE;
  59                                 carry = 1;
  60                         } else {
  61                                 res._digits[i] = r;
  62                                 carry = 0;
  63                         }
  64                 }
  65                 assert(carry == 0);
  66                 return res;
  67         }
  68
  69         void print() {
  70                 bool zero = true;
  71                 dforn (i, BigInt_NDIGITS) {
  72                         if (zero) {
  73                                 if (_digits[i] == 0) continue;
  74                                 printf("%u", _digits[i]);
  75                                 zero = false;
  76                         } else {
  77                                 printf("%.8u", _digits[i]);
  78                         }
  79                 }
  80                 if (zero) {
  81                         printf("0");
  82                 }
  83         }
  84
  85 private:
  86         // Least significant digit first.
  87         // Digits are in 0 <= d < BigInt_BASE
  88         vector<uint32> _digits;
  89 };
  90
  91 #define print_bigint(x) (x).print()
  92
  93 typedef vector<BigInt> vBigInt;
  94 typedef vector<vBigInt> vvBigInt;
  95 BigInt distinct_subsequences(const string& x, const string& z) {
  96         vvBigInt m(2, vBigInt(z.size() + 1, BigInt(0)));
  97
  98         m[0][0] = BigInt(1);
  99         m[1][0] = BigInt(1);
 100         bool row = 1;
 101         forsn (i, 1, x.size() + 1) {
 102                 forsn (j, 1, z.size() + 1) {
 103                         if (x[i - 1] == z[j - 1]) {
 104                                 m[row][j] = m[!row][j] + m[!row][j - 1];
 105                         } else {
 106                                 m[row][j] = m[!row][j];
 107                         }
 108                 }
 109                 row = !row;
 110         }
 111         return m[!row][z.size()];
 112 }
 113
 114 int main(int argc, char **argv) {
 115         uint32 n;
 116         cin >> n;
 117         char c;
 118         cin.get(c);
 119         forn (i, n) {
 120                 string x, z;
 121                 getline(cin, x);
 122                 getline(cin, z);
 123                 print_bigint(distinct_subsequences(x, z));
 124                 cout << endl;
 125         }
 126         return 0;
 127 }
 128